COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00003 00003	\section{Propositional terms.}
C00017 00004	\section{The function {\it eval}.}
C00035 00005	        Since any computation can be described as evaluating an expression
C00039 00006	        When you talk to \lisp\ you do not explicitly tell the interpreter
C00041 00007		Lisp is a programming language for computing with the
C00046 00008	% The old allsubsub section from writin
C00064 00009	% Another definition of subst
C00065 ENDMK
C⊗;

        The value of a propositional term can be determined using the truth 
table given in \tabref{propop}.  

\begin{table}
\label{propop}

$$\vbox{\halign{$#$\hfil&\qquad$#$\hfil&\qquad$#$\hfil\cr
      \qT \qand \qT  = \qT & \qT \qor \qT  = \qT\cr
      \qT \qand \qNIL = \qNIL  & \qT \qor \qNIL = \qT &  \qnot \qT  = \qNIL\cr
     \qNIL \qand \qT  = \qNIL &     \qNIL \qor \qT  = \qT \qnot \qNIL = \qT\cr
     \qNIL \qand \qNIL = \qNIL &     \qNIL \qor \qNIL = \qNIL  \cr
}}$$

\caption{Truth table for propositional terms.}
\end{table}

\section{Propositional terms.}
\label{andor}

        As mentioned in the previous section,
propositional terms are a terms whose value represents a truth value.
The simplest propositional terms are the constants \qT\ and \qNIL.  
If \qp is a predicate of n-arguments then $\qp[x_1,\ \ldots\ x_n]$ is a 
propositional term.  Additional propositional terms can be formed by combining 
terms already formed using the logical operations of
conjunction(\qand), disjunction(\qor) and negation(\qnot).
Both \qand\ and \qor\ are associative, so we can write expressions
like $p_1 \qand p_2 \qand p_3$ without worrying about the grouping.  

        The evaluation of propositional terms is defined using conditional 
terms as follows:
%
$$\vbox{\ialign{\hfil $#$&$\>=#$\hfil\cr
  p \qand q & \qif p \qthen q \qelse \qNIL\cr
  p \qor q & \qif p \qthen p \qelse q\cr
  \qnot p & \qif p \qthen \qNIL \qelse \qT\cr
}}$$
%
The internal forms of these definitions are
%
$$\vbox{\halign{\hfil \sx # &$=$\ \sx #\hfil\cr
     (AND P Q) & (COND (P Q) (T NIL))\cr
      (OR P Q) & (COND (P P) (T Q))  \cr
       (NOT P) & (COND (P NIL) (T T))\cr
}}$$
%
Note that if $p$ is false then $p \qand q = \qNIL$ independent of the value of
$q$, and likewise if $p$ is true, then $p \qor q = \qT$ is independent of
$q$.  If $p$ has been evaluated and found to be false, then $q$ does
not have to be evaluated at all to find the value of $p \qand q$, and, in
fact, \LISP does not evaluate $q$ in this case.  Similarly, $q$ is not
evaluated in evaluating $p \qor q$ if $p$ is true. This procedure is in
accordance with the above conditional expression descriptions of
these operators.  The importance of this convention, which contrasts
with that of ALGOL 60, will be apparent later when we discuss
recursive definitions of functions and predicates.  

        Propositional expressions can be combined with functions and conditional
expressions to get terms like
%
$$\qif [\qn u \qor \qn \qd u] \qthen u \qelse \qa u \qcons {\it alt} \qdd u$$
%
whose internal form is
%
$$|(IF (OR (NULL U) (NULL (CDR U))) U  (CONS (CAR U) (ALT (CDDR U))))|.$$

        We conclude this section with two remarks.  First, the only 
S-expressions that we have said represent truthvalues are \qT\ and \qNIL.
However, \LISP implementations regard any non-\qNIL\ S-expression as
representing \qtrue.  \LISPs doesn't distinguish between between 
propositional terms and more general terms.  Thus any term can appear in
the $p$ part of a conditional term.  Second, 
\LISP implementations allow \qand\ and \qor\ to have arbitrary numbers
of arguments.

\section{Propositional terms.}
\label{andor}

        As mentioned in the previous section,
propositional terms are a terms whose value represents a truth value.
The simplest propositional terms are the constants \qT\ and \qNIL.  
If \qp is a predicate of n-arguments then $\qp[x_1,\ \ldots\ x_n]$ is a 
propositional term.  Additional propositional terms can be formed by combining 
terms already formed using the logical operations of
conjunction(\qand), disjunction(\qor) and negation(\qnot).
Both \qand\ and \qor\ are associative, so we can write expressions
like $p_1 \qand p_2 \qand p_3$ without worrying about the grouping.  

        The evaluation of propositional terms is defined using conditional 
terms as follows:
%
$$\vbox{\ialign{\hfil $#$&$\>=#$\hfil\cr
  p \qand q & \qif p \qthen q \qelse \qNIL\cr
  p \qor q & \qif p \qthen p \qelse q\cr
  \qnot p & \qif p \qthen \qNIL \qelse \qT\cr
}}$$
%
The internal forms of these definitions are
%
$$\vbox{\halign{\hfil \sx # &$=$\ \sx #\hfil\cr
     (AND P Q) & (COND (P Q) (T NIL))\cr
      (OR P Q) & (COND (P P) (T Q))  \cr
       (NOT P) & (COND (P NIL) (T T))\cr
}}$$
%
Note that if $p$ is false then $p \qand q = \qNIL$ independent of the value of
$q$, and likewise if $p$ is true, then $p \qor q = \qT$ is independent of
$q$.  If $p$ has been evaluated and found to be false, then $q$ does
not have to be evaluated at all to find the value of $p \qand q$, and, in
fact, \LISP does not evaluate $q$ in this case.  Similarly, $q$ is not
evaluated in evaluating $p \qor q$ if $p$ is true. This procedure is in
accordance with the above conditional expression descriptions of
these operators.  The importance of this convention, which contrasts
with that of ALGOL 60, will be apparent later when we discuss
recursive definitions of functions and predicates.  

        Propositional expressions can be combined with functions and conditional
expressions to get terms like
%
$$\qif [\qn u \qor \qn \qd u] \qthen u \qelse \qa u \qcons {\it alt} \qdd u$$
%
whose internal form is
%
$$|(IF (OR (NULL U) (NULL (CDR U))) U  (CONS (CAR U) (ALT (CDDR U))))|.$$

        We conclude this section with two remarks.  First, the only 
S-expressions that we have said represent truthvalues are \qT\ and \qNIL.
However, \LISP implementations regard any non-\qNIL\ S-expression as
representing \qtrue.  \LISPs doesn't distinguish between between 
propositional terms and more general terms.  Thus any term can appear in
the $p$ part of a conditional term.  Second, 
\LISP implementations allow \qand\ and \qor\ to have arbitrary numbers
of arguments.

\section{The function {\it eval}.}
\label{evaluator}

        \mkop{eval} plays both a theoretical and a practical role in \lisp.
Historically, the list notation for \lisp\ functions and \mkop{eval} were first
devised in order to show how easy it is to define a universal function in \lisp\ -
the idea was to advocate \lisp\ as an alternative to Turing machines for doing
the elementary theory of computability.  This role will be discussed in a later
chapter.   S. R. Russell noted that
\mkop{eval} could serve as an interpreter for \lisp\ and promptly programmed it
in machine language with minor modifications to make it more practical.
An interpreter based on \mkop{eval} has remained a feature of most \lisp\ systems.
Thus when you talking to \lisp\ the system is in a loop that \mkop{read}s what you
type, \mkop{eval}s it and \mkop{print}s the result.   [Of course a real \lisp\ system
does many other things too, such a storage management, error handling, 
etc.]

        \mkop{eval} for \lisp\ expressions is analogous to the
interpreter \mkop{numval} for arithmetic expressions given in \defref{numval}.
The first argument to \mkop{eval} is a \lisp\ expression
in internal notation.  The second argument is an association list that
tells \mkop{eval} what value each variable has, and what function definition
is to be associated with each function name.  Thus the association list is 
a list of pairs where each pair consists either of a variable and the S-expression 
corresponding to its value, or a function name and the S-expression
representing the function expression defining the function.  
(Here a function expression is either a function name, or a lambda expression.)
The result of applying \mkop{eval} is the value of the term represented by the
S-expression in an
environment where the free variables are assigned the values given by
the association list and where the function names occuring free (i.e. not
bound in a label expression) denote functions defined by the associated 
expressions in the association list.

        Since any computation can be described as evaluating an expression
without free variables or function names, the second argument theoretically
plays a role mainly in the recursive definition of \mkop{eval}.  Thus 
we usually start our computations with the second argument \qNIL.

        To illustrate this, suppose we want to apply the function \mkop{alt}
to the list |(A B C D E)|, i.e. we wish to evaluate $\mkop{alt}[|(A B C D E)|]$.
This can be obtained by computing
$$\vbox{\ialign{\hfil$#$&&\sx #\hfil\cr
  \mkop{eval}[&(ALT (QU&OTE (A &B C D E))),\cr
              &((ALT LA&MBDA (X&)\cr
              &        &(COND (&(OR (NULL X) (NULL (CDR X))) X)\cr
              &        &       &(T (CONS (CAR X) (ALT (CDDR X)))))))$]$.\cr
}}$$

        A simplified version of the usual \lisp\ \mkop{eval} is the following:
$$\edefun{eval}{%
}$$
%  ∂(n)⊗⊗eval[e, a] ←⊗
%  ∂(n+4)       ⊗⊗qif qat e qthen [qif numberp e qor e  = qNIL qor e = qT qthen e 
%  qelse qd assoc[e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qat qa e qthen⊗
%  ∂(n+8)               ⊗⊗[qif qa e = $QUOTE qthen qad e⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $COND qthen evcond[qd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $LIST qthen evlist[qd e,a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CAR qthen qa eval[qad e, a]⊗
%  !fcneval&l ∂(n+8)⊗⊗qelse qif qa e = $CDR qthen qd eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CONS qthen eval[qad e, a] . eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $ATOM qthen qat eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $EQ qthen  eval[qad e, a] qeq eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse eval[qd assoc[qa e, a] . qd e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LAMBDA qthen eval[qadda e, prup[qada e, evlist[qd e,a]] * a]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LABEL qthen eval[qadda e . qd e, [qada e . qadda e] . a]⊗, 
%  
%  where the auxiliary functions ⊗evcond and ⊗evlist are defined by
%  
%  !fcnevcond&  ⊗⊗⊗evcond[u, a] ← qif eval[qaa u, a] qthen eval[qada u, a]  qelse evcond[qd u, a]⊗, 
%  
%  !fcnevlist&  ⊗⊗⊗evlist[u, a] ← qif qn u qthen qNIL qelse eval[qa u,a] . evlist[qd u, a]⊗,
%  
%  and the auxiliary function ⊗prup, used for pairing up the elements of two
%  lists of equal length, is defined by
%  
%  !fcnprup&  ⊗⊗⊗prup[u, v] ← qif qn u qthen qNIL qelse [qa u . qa v] . prup[qd u,qd v]⊗.
%  Recall that ⊗assoc is defined by
%  
%  !eqnassoc1  ⊗⊗⊗assoc[x,a] ← qif qn a qthen qNIL qelse qif qaa a qeq x qthen qa a qelse assoc[x,qd a].⊗

        This simple \mkop{eval} expects that an expression is either a
constant ({\it number}, \qT, \qNIL, or a |QUOTE|d S-expression),
a variable whose value can be found on the association list, 
a conditional expression, a list making
expression, or an application of a function or lambda expression
to a list of arguments.  Thus \mkop{eval} checks to see
which of the above classes the expression to be evaluated falls into
and proceeds accordingly.  If the expression, $e$, is atomic then it is either
a non |QUOTE|d constant or a variable.  If the former then \mkop{eval} just returns
the expression, if the latter it looks up the value on the association list, $a$.  

        If $e$ is non-atomic but $\qa e$ is atomic then $e$ is either
a |QUOTE|d constant, a conditional, a list maker, or an application of a
function to a list of arguments.  In the constant case the expression
being quoted ($\qad e$) is returned.  If $e$ is a conditional then the list
of pairs is processed by the auxiliary evaluator \mkop{evcond}, which 
\mkop{eval}s the ``if'' parts ($\qaa u$) in order until a true one is found then
returns the result of \mkop{eval}ing the corresponding ``then'' part ($\qada u$).
In the list case the list of expressions to be evaluated
is given to \mkop{evlist} which returns a list of the values.
In the function application case there are two 
possibilities.  If the function to be applied
is one of the elementary functions, the indicated operation is performed
on the result of evaluating the arguments.  Otherwise the function must
be defined in $a$, so \mkop{eval} looks up the definition, replaces the function 
name by the function definition in the expression and restarts the evaluation.

        If neither $e$ nor $\qa e$ are atomic then it must be a lambda 
application.  In the lambda case the argument list is given to \mkop{evlist} to
be evaluated, the values are then paired with the list of variables to be
bound by the lambda ($\qada e$) using \mkop{prup} and put on the front of $a$. 
The body of the lambda ($\qadda e$) is then evaluated using this new 
association list. 

        If $e$ is not an expression of the sort expected by \mkop{eval}, then
the result is not defined.   It would not be difficult to add additional
clauses to \mkop{eval} so that it would return reasonable error messages rather
than just being undefined (or dying in some strange way as would be
likely in an actual computer).  It would be necessary to be make the
error messages distinguishable from legitimate values of the expression
so that errors at inner levels of evaluation could be passed up the chain.
This could be done by returning legitimate values as pairs whose first
element is one atom and error messages as pairs prefixed by another.
Terms containing \mkop{eval} would have to distinguish the cases.

       Notice that 
|COND| and |LIST| considered as pseudo-functions behave differently
than ordinary functions in that both can take
an arbitrary number of arguments while functions defined by a lambda
expression have a fixed number of arguments determined by the variable list
occuring in the lambda expression.  Also, the usual manner of evaluation
an application term is \lisp\ is to evaluate all of the arguments then
apply the function.  This will not work for |COND| as the main reason for
a conditional is to be able to select a term to evaluate depending on
some set of conditions and not to evaluate other terms under those conditions.

        The above version of \mkop{eval} does not handle the propositional
constructs \qand, \qor, and \qnot.  The effect of these constructs
can be obtained by appropriate use of the condtional, but simply
defining functions for \qand\ and \qor\ will not work as the evaluation
of a function application requires that all of the arguments of 
of the function be evaluated before it is applied while the specification
of \qand\ and \qor\ require that only as many of the arguments be evaluated
as are required to determine the answer.  
Another problem is that in most implementations 
they are allowed to take an arbitrary number of arguments.   Thus
we need to build them into \mkop{eval} for things to work properly.
We will see later that \lisp\ systems provide alternate solutions to
this problem by providing a variety of modes of function application.
(These are known as |EXPR| and |LEXPR|s.)   Macros are also
used for this purpose and will be explained later.  Arithmetic is
also missing from our \mkop{eval}.  Adding these constructs is essentially
like combining \mkop{eval} with the earlier evaluator \mkop{numval} and adding
any additional primitive operations that are desired.

        We note that \mkop{eval} can evaluate itself if it is given an
association list, $eval-alist$, containing the definition of \mkop{eval}
represented as s-expressions.  Thus
$$\mkop{eval}[|(EVAL '(CAR '(A.B)) NIL)|,eval-alist] = |A|.$$

        When you talk to \lisp\ you do not explicitly tell the interpreter
what association list to use generally.  This is because 
the \lisp\ associates with each atom a list of properties,  among these
are the value, and/or the function definition associated with that
atom.  The \lisp\ interpreter typically
looks up variable values and function definitions on the corresponding 
property lists.  Thus, instead of making up an association list
with the appropriate variables and functions defined, the property
lists must first be primed by doing |SETQ|s for giving variables
initial values and |DEFUN|s for any functions
that need to be defined.  These features will be discussed in
more detail in \chapref{IMPURE}.

\subsubsection*{Exercises}
\begin{list}{\arabic{list}.}{\leftmargin0pt \labelwidth -\parindent}

\item What is the value of 
$$\vbox{\ialign{\hfil$#$&$#$\hfil\cr
  \mkop{eval}[&|(LEFT (QUOTE (A . B)))|,\cr
              &|((LEFT LAMBDA (X) (COND ((ATOM X) X) (T (LEFT (CAR X))))))|]?\cr
}}$$

\item Translate the definition of \mkop{eval} given above into internal notation.

\item  Go to your nearest \lisp\ system, type in your answer to the second exercise
and use it to check your answer to the first exercise.

\end{list}
        Since any computation can be described as evaluating an expression
without free variables or function names, the second argument theoretically
plays a role mainly in the recursive definition of \mkop{eval}.  Thus 
we usually start our computations with the second argument \qNIL.

        To illustrate this, suppose we want to apply the function \mkop{alt}
to the list |(A B C D E)|, i.e. we wish to evaluate $\mkop{alt}[|(A B C D E)|]$.
This can be obtained by computing
$$\vbox{\ialign{\hfil$#$&&\sx #\hfil\cr
  \mkop{eval}[&(ALT (QU&OTE (A &B C D E))),\cr
              &((ALT LA&MBDA (X&)\cr
              &        &(COND (&(OR (NULL X) (NULL (CDR X))) X)\cr
              &        &       &(T (CONS (CAR X) (ALT (CDDR X)))))))$]$.\cr
}}$$

$$\edefun{eval}{%
}$$
%  ∂(n)⊗⊗eval[e, a] ←⊗
%  ∂(n+4)       ⊗⊗qif qat e qthen [qif numberp e qor e  = qNIL qor e = qT qthen e 
%  qelse qd assoc[e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qat qa e qthen⊗
%  ∂(n+8)               ⊗⊗[qif qa e = $QUOTE qthen qad e⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $COND qthen evcond[qd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $LIST qthen evlist[qd e,a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CAR qthen qa eval[qad e, a]⊗
%  !fcneval&l ∂(n+8)⊗⊗qelse qif qa e = $CDR qthen qd eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CONS qthen eval[qad e, a] . eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $ATOM qthen qat eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $EQ qthen  eval[qad e, a] qeq eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse eval[qd assoc[qa e, a] . qd e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LAMBDA qthen eval[qadda e, prup[qada e, evlist[qd e,a]] * a]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LABEL qthen eval[qadda e . qd e, [qada e . qadda e] . a]⊗, 
%  
%  where the auxiliary functions ⊗evcond and ⊗evlist are defined by
%  
%  !fcnevcond&  ⊗⊗⊗evcond[u, a] ← qif eval[qaa u, a] qthen eval[qada u, a]  qelse evcond[qd u, a]⊗, 
%  
%  !fcnevlist&  ⊗⊗⊗evlist[u, a] ← qif qn u qthen qNIL qelse eval[qa u,a] . evlist[qd u, a]⊗,
%  
%  and the auxiliary function ⊗prup, used for pairing up the elements of two
%  lists of equal length, is defined by
%  
%  !fcnprup&  ⊗⊗⊗prup[u, v] ← qif qn u qthen qNIL qelse [qa u . qa v] . prup[qd u,qd v]⊗.
%  Recall that ⊗assoc is defined by
%  
%  !eqnassoc1  ⊗⊗⊗assoc[x,a] ← qif qn a qthen qNIL qelse qif qaa a qeq x qthen qa a qelse assoc[x,qd a].⊗
        When you talk to \lisp\ you do not explicitly tell the interpreter
what association list to use generally.  This is because 
the \lisp\ associates with each atom a list of properties,  among these
are the value, and/or the function definition associated with that
atom.  The \lisp\ interpreter typically
looks up variable values and function definitions on the corresponding 
property lists.  Thus, instead of making up an association list
with the appropriate variables and functions defined, the property
lists must first be primed by doing |SETQ|s for giving variables
initial values and |DEFUN|s for any functions
that need to be defined.  These features will be discussed in
more detail in \chapref{IMPURE}.
	Lisp is a programming language for computing with the
symbolic expressions that arise in artificial intelligence and
in computation with mathematical formulas.  The core of the
language is called pure Lisp and we begin with that.  Pure
Lisp is most clearly explained rather abstractly.  The data
of Lisp are called S-expressions.

	Begin with a set {\it A} called the set of atoms.  For our
present purpose it doesn't matter what the atoms are.  We only
need to provide a test for equality of two atoms and a predicate
for telling whether an object is an atom.  In this section we'll
use $=$ for equality, e.g we write $x = y$, and $\qat$ for the
atom test.  Because, we will need parentheses for Lisp S-expressions,
we use square brackets for applying a function to arguments.
Thus we write $\qat[x]$ for the assertion that {\it x} is an
atom.  However, when there is no ambiguity, we reduce the number
of brackets by omitting them for functions of one argument.  Thus
we simply write $\qat x$.

	S-expressions are built up from atoms by the following rule.

	{\it An atom is an S-expression, and an ordered pair of
S-expressions is an S-expression.  All S-expressions are formed
in this way.}

	From this abstract point of view we need say nothing about
how S-expressions are represented in the memory of a computer or
on paper.  We do need names for the basic operations on S-expressions.
The operation that forms pairs is called {\it cons} in Lisp.  Thus if
{\it x} and {\it y} are S-expressions, then $cons[x,y]$ is the
pair whose first and second elements are {\it x} and {\it y} respectively.
It is also written $x\qcons y$ when an infix notation is
more convenient.  The operations for taking the components of a pair
are called {\it car} and {\it cdr}.  We write $car[x]$ and $cdr[x]$
or more briefly $\qa\ x$ and $\qd\ x$.  We have the equations
%
	$$car[cons[x,y]] = x$$
%
and
%
	$$cdr[cons[x,y]] = y$$
%
or in the shorter notation
%
	$$\qa\ [x\qcons y] = x$$
%
and
%
	$$\qd\ [x\qcons y] = y.$$
%
We apologize for all these variant notations, but they exist for
historical reasons, and they are all needed to read this book and
other Lisp literature.

	We need a notation for constant S-expressions.  For the
moment we'll use capital letters for atoms, so that {\sx A},
{\sx B}, etc. denote atoms.  The pairs are formed by surrounding
the paired items by parentheses and separating them with a dot.
Thus {\sx A}, {\sx (A.A)}, {\sx (A.B)} and {\sx ((A.B).(A.(B.C)))}
are all S-expressions.  It is important to distinguish the
operation {\it cons} or $\qcons$ that forms S-expressions from
the dot used in writing S-expressions.  The former is an operation
that can be executed, i.e. a program getting {\it x} and {\it y},
computes $x\qcons y$, whatever $x$ and $y$ may be, while {\sx (A.B)}
just denotes that one S-expression.  We have
%
	$${\sx A}\qcons {\sx B} = {\sx (A.B)},$$
%
but we can't write $(x.y)$.  Notice that $\qcons$ is a raised dot.

	We also postulate that a pair is never an atom, and this is
expressed by the formula
%
	$$¬\qat[x\qcons y].$$
% The old allsubsub section from writin
	The problem has to do with ``lists of lists'' or L-lists.  An L-list
is either the empty list, or an atom /cons\//ed onto the front of
an L-list, or an L-list /cons\//ed onto the front of an L-list.   Thus
|(A (A B) C)| is an L-list, but |(A (B . C) D)| is not.   Although
this class of S-expressions is less general than the usual LISP notion
of list, it is more uniform.  The
computation of a function on L-lists may use the value of the function
on the /car\// of the L-list (when it is non-atomic) as well as on the 
/cdr\// as both are again L-lists.

	The function /allsubsub\// returns a list of all occurrences of an 
L-list /u\// as a sublist or as a sublist of a sublist of an L-list /v/.  
For example |(A A)| occurs three times as a subsublist of |(A A A B A A)|
and |(A)| occurs 4 times in |(A (B (A A)) (C (((A)))))|.

	We begin with a simpler function restricted to lists of atoms.
Thus we wish to compute the function /allsub\// that returns a list of all 
occurrences of a list of atoms /u\// as a sublist of another list of atoms /v\//.  
The first thing to do is decide on the representation of an
occurrence of one list as a sublist of another list.  In the case of 
lists of atoms, a fairly natural solution is to represent an occurrence of a
particular sublist as the number /n\// corresponding to position in the list 
of the beginning of that occurrence.  Thus  
\beginfundef 
/allsub\//[|(A A),(A A A B A A)|] = |(1 2 5)|.
\endfundef 

	To compute $/allsub\//[/u/,/v\//]$, 
if /v\// is \qNIL\ then the answer is \qNIL.
Otherwise, imagine that we know the answer for \qd /v/.
Then there are two possiblities.
Either /u\// ``agrees with'' /v\// (/v\// 
may be longer than /u/, but up to the end of /u\//
the elements of /v/ and /u/ are the same), or not.  If not, the answer is
just the result for \qd /v/, otherwise we add the current
position to the result for \qd /v/.  This analysis
suggests that we will need an additional argument to keep track of
the current position.  Thus we define a function $/allsub1/[/u/,/v/,/p\//] $
where the argument /p\// is intended to correspond to the position of
the argument /v\// in the initial list.  If /v\// is \qNIL\ then the
result is \qNIL.  Otherwise suppose we know the value of 
$/allsub1/[/u/,\qd /v/,/p/+1]$
then we either add /p\// onto that value or return it unchanged according to
whether or not /u\// agrees with /v\//.  Assuming we have a suitable definition of 
/agrees\//, the above analysis leads to the following definitions:
\beginlisp
(bb tex '(allsub allsub1))
\endlisp
\beginfundef 
\funlab{fcnallsub}
\vbox{
\hbox{\hskip0\unit $/allsub/[/u/, /v\//] ← /allsub1/[/u/, /v/, 1]$}
\medskip
\hbox{\hskip0\unit $/allsub1/[/u/, /v/, /p\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /agrees/[/u/, /v\//] \qthen  $}
\hbox{\hskip8\unit $        /p/ \qcons  /allsub1/[/u/, \qd /v/, /add1/ 
/p\//]$}
\hbox{\hskip4\unit $    \qelse  /allsub1/[/u/, \qd /v/, /add1/ /p\//]$}
}
\endfundef 

	It remains for us to write the definition of
$/agrees/[/u/,/v\//]$ 
which determines whether or not /u\// matches the beginning of /v/.  
This is easy.  If /u\// is \qNIL\ then we have gotten to the end of /u\// 
without 
finding a disagreement and we return \qT.   If /v\// is \qNIL\ (and /u\// is not)
then we return \qNIL\ and /u\// does not agree with the beginning of /v/.  
Otherwise the result is \qT\ only if $\qa/u/=\qa/v/$ 
and the /cdr\//s of /u\// and /v\// 
agree.  Thus
\beginlisp
(bb tex '(agrees))
\endlisp
\beginfundef 
\funlab{fcnagrees}
\vbox{
\hbox{\hskip0\unit $/agrees/[/u/, /v\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /u/ \qthen  \qT $}
\hbox{\hskip4\unit $    \qelsif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelse  \qa /u/ \qequal \qa /v/ \qand /agrees/[\qd 
/u/, \qd /v\//]$}
}
\endfundef 
The internal forms of the above definitions are
{\tt\obeyspaces\obeylines
    (DEFUN ALLSUB (U V) (ALLSUB1 U V 1)) 

    (DEFUN ALLSUB1 (U V P) 
           (COND ((NULL V) NIL)
                 ((AGREES U V) (CONS P (ALLSUB1 U (CDR V) (ADD1 P))))
                 (T (ALLSUB1 U (CDR V) (ADD1 P))))) 

    (DEFUN AGREES (U V) 
           (COND ((NULL U) T)
                 ((NULL V) NIL)
                 (T (AND (EQUAL (CAR U) (CAR V))
                         (AGREES (CDR U) (CDR V)))))) 
}

	Now we return to the /allsubsub\// problem. 
As with the simpler case, we must first decide how to represent an occurrence 
of an L-list as a subsublist of an L-list.  Again we need only represent the
position where the list comparison begins.  Consider an arbitrary point, /p/,  in an
L-list.  Either it is an element of the list, or is contained in one of the
elements of the list.  In the first case the position /n\// of the element is
sufficient, in the second case we need the position /n\// of the element together
with the position of the point /p\// relative to that element.
Thus in the first case we take the list containing only the number /n\// and
in the second case we add /n\// onto the list representing the position of /p\// 
in the /n\//th element of the list.  Using this representation we have
\beginfundef 
/allsubsub/[|(A),(A (B (A A)) (C (((A)))))|] = |((1) (2 2 1) (2 2 2) (3 2 1 1 1))|.
\endfundef 

	To construct the desired list of positions we check for a agreement of 
/u\// 
at each position and add matching positions to the result.   (Actually 
we will see that some positions can be ruled out with out explicitly checking 
for agreement.)  In particular, we will need to pass around sufficient information
to be able to construct a representation of the current position whenever an
agreement
is found.  Let us consider the simpler problem of computing $/allpos/[/v\//]$, a list
of all the positions in /v/.  A program for this  can easily be modified 
to list only those positions satisfying the ``agrees'' condition.
A definition of /allpos\// can be obtained by recalling the discussion about of how
a position is to be represented.  Namely if /n\// is the position of /v\// 
in the list of which /v\// is a tail then
(i) if /v\// is \qNIL\ then there are no positions and the answer is \qNIL,
(ii) \qa/v\// is an atom then add $<n>$ to the list of positions in \qd /v\//
passing $n+1$ as the current position number
(iii) otherwise compute the list of positions in \qa/v\// (relative to \qa/v\//),
tack /n\// onto the front of each position, append this onto the list of
positions in \qd /v\// (again passing $n+1$) and finally add the current
position, $<n>$, to the result.   Thus we have
\beginlisp
(bb tex '(allpos allpos1 tack))
\endlisp
\beginfundef 
\funlab{fcnallpos}
\vbox{
\hbox{\hskip0\unit $/allpos\// /v\// ← /allpos1\//[/v\//, 1]$}
\medskip

\hbox{\hskip0\unit $/allpos1\//[/v\//, /n\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v\// \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v\// \qthen  </n\//> \qcons 
 /allpos1\//[\qd /v\//, /add1\// /n\//]$}
\hbox{\hskip4\unit $    \qelse  </n\//> \qcons  [/tack\//[/n\//, /allpos\// 
\qa /v\//] * /allpos1\//[\qd /v\//, /add1\// /n\//]]$}
\medskip

\hbox{\hskip0\unit $/tack\//[/n\//, /w\//] ← \qif  \qn /w\// \qthen  \qNIL 
 \qelse  [/n\// \qcons  \qa /w\//] \qcons  /tack\//[/n\//, \qd /w\//]$}
}
\endfundef 

Now we modify to /allpos\// and /allpos1\// to carry around the parameter /u\// 
and rule out those positions that don't agree.  In particular
we only add $<n>$ to the list if $/agrees/[/u/,/v\//]$ is satisfied, and in
this case we don't look for agreement in \qa/v\// as the top level
match makes this impossible (recall our lists are finite tree-like structures).
So we arrive at the following:
\beginlisp
(bb tex '(allsubsub allsubsub1))
\endlisp
\beginfundef 
\funlab{fcnallsubsub}
\vbox{
\hbox{\hskip0\unit $/allsubsub\//[/u\//, /v\//] ← /allsubsub1\//[/u\//, 
/v\//, 1]$}
\medskip

\hbox{\hskip0\unit $/allsubsub1\//[/u\//, /v\//, /n\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v\// \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /agrees\//[/u\//, /v\//] \qthen  </n\//> 
\qcons  /allsubsub1\//[/u\//, \qd /v\//, /add1\// /n\//]$}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v\// \qthen  /allsubsub1\//[/u\//, 
\qd /v\//, /add1\// /n\//]$}
\hbox{\hskip4\unit $    \qelse  /tack\//[/n\//, /allsubsub\//[/u\//, \qa 
/v\//]] * /allsubsub1\//[/u\//, \qd /v\//, /add1\// /n\//]$}
}
\endfundef 

An alternate solution for the /allpos\// and the /allsubsub\// problems
is to pass along a complete representation of the current position.  
When we pass it in the \qd /v\// direction we need to add 1 to the
last element and when we pass it in the \qa/v\// direction we need to
add a 1 to the end of the list.  Since all of the action is at the
end of the list it is easier to pass along the reverse of the position
list and re-reverse it when returning the position as an answer.  
Thus we get the following definitions 
\beginlisp
(bb tex '(allpos% allpos1% allsubsub% allsubsub1%))
\endlisp
% Don't forget to remove the % signs from the following defs
\beginfundef 
\funlab{fcnallpos1}\funlab{fcnallsubsub1}
\vbox{
\hbox{\hskip0\unit $/allpos/ /v/ ← /allpos1/[/v/, |(1)|]$}
\medskip
\hbox{\hskip0\unit $/allpos1/[/v/, /p\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v/ \qthen  $}
\hbox{\hskip8\unit $        /reverse/ /p/ \qcons  /allpos1/[\qd /v/, /add1/ 
\qa /p/ \qcons  \qd /p\//]$}
\hbox{\hskip4\unit $    \qelse  /reverse/ /p/$}
\hbox{\hskip10\unit $          \qcons  [/allpos1/[\qa /v/, 1 \qcons  /p\//]$}
\hbox{\hskip13\unit $             * /allpos1/[\qd /v/, /add1/ \qa /p/ 
\qcons  \qd /p\//]]$}
\medskip
\hbox{\hskip0\unit $/allsubsub/[/u/, /v\//] ← /allsubsub1/[/u/, /v/, |(1)|]$}
\medskip
\hbox{\hskip0\unit $/allsubsub1/[/u/, /v/, /p\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /v/ \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelsif  /agrees/[/u/, /v\//] \qthen  $}
\hbox{\hskip8\unit $        /reverse/ /p/ \qcons  /allsubsub1/[/u/, \qd 
/v/, /add1/ \qa /p/ \qcons  \qd /p\//]$}
\hbox{\hskip4\unit $    \qelsif  \qat \qa /v/ \qthen  /allsubsub1/[/u/, 
\qd /v/, /add1/ \qa /p/ \qcons  \qd /p\//]$}
\hbox{\hskip4\unit $    \qelse  /allsubsub1/[/u/, \qa /v/, 1 \qcons  /p\//]$}
\hbox{\hskip10\unit $          * /allsubsub1/[/u/, \qd /v/, /add1/ \qa 
/p/ \qcons  \qd /p\//]$}
}
\endfundef 

Notice that in the first solution, the construction of the position representation
was taken care of somewhat automatically by the recursive structure of the program,
while in the second case we had to worry about the details of constructing
the position representations.

In both cases the computation works by passing information both down and across
the list structure and getting results back.  What is passed on and the 
interpretation of the result returned depends on the direction. 
In this example there is no exchange of information between the subcomputations.
In a more complicted situation this might also be necessary.

% Another definition of subst
\beginlisp
(DEFUN SUBST (X Y Z) 
   (COND ((ATOM Z) (COND ((EQ Y Z) X) (T Z)))
	 (T (LET ((Z1 (SUBST X Y (CAR Z))) (Z2 (SUBST X Y (CDR Z))))
		 (COND ((AND (EQ Z1 (CAR Z)) (EQ Z2 (CDR Z))) Z)
		       (T (CONS Z1 Z2)))))))
(bb tex '(subst))
\endlisp
\beginfundef
\xx{0} subst[x, y, z] ← \cr
\xx{4}     \qif  \qat z \qthen  [\qif  y \qeq z \qthen  x \qelse  z]\cr
\xx{4}     \qelse  \qlet  z1 ← subst[x, y, \qa z], z2 ← subst[x, y, \qd 
z] \cr
\xx{8}         \qin  \qif  z1 \qeq \qa z \qand z2 \qeq \qd z \qthen  z 
\qelse  z1 \qcons  z2\cr